//你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能
//折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。 
//
// 如果你能使这个正方形，则返回 true ，否则返回 false 。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: matchsticks = [1,1,2,2,2]
//输出: true
//解释: 能拼成一个边长为2的正方形，每边两根火柴。
// 
//
// 示例 2: 
//
// 
//输入: matchsticks = [3,3,3,3,4]
//输出: false
//解释: 不能用所有火柴拼成一个正方形。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= matchsticks.length <= 15 
// 1 <= matchsticks[i] <= 10⁸ 
// 
// Related Topics位运算 | 数组 | 动态规划 | 回溯 | 状态压缩 
//
// 👍 440, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class MatchsticksToSquare {
    public static void main(String[] args) {
        Solution solution = new MatchsticksToSquare().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[] cur;
        int tar;

        // DFS + 记忆化搜索 和 698一样
        public boolean makesquare(int[] matchsticks) {
            int sum = Arrays.stream(matchsticks).sum();
            if (sum % 4 != 0) return false;
            this.tar = sum / 4;
            this.cur = new int[4];
            Arrays.sort(matchsticks);
            return backTracking(matchsticks, matchsticks.length - 1);
        }

        public boolean backTracking(int[] matchsticks, int i) {
            if (i < 0) return true;
            for (int j = 0; j < 4; j++) {
                if (j > 0 && cur[j] == cur[j - 1]) continue;
                cur[j] += matchsticks[i];
                if (cur[j] <= tar && backTracking(matchsticks, i - 1)) return true;
                cur[j] -= matchsticks[i];
            }

            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
